package alo;

import java.util.*;
/**
 * @ClassName test1
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/4/12 9:38
 * @Version 1.0
 */



/**
 * @description: 牛客网的设计LRU缓存结构，用例通过率100%，耗时2.5s，占用内存191MB
 * @author: pilaf
 * @create: 2020-12-09 12:26
 */
public class LRUSolution {

    private LinkedHashMap<Integer, Integer> linkedHashMap;

    /**
     * 自定义一个LinkedHashMap子类，主要是增加了固定容量的限制
     * @param <K>
     * @param <V>
     */
    private static class FixedCapacityLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
        private int fixedCapacity;

        public FixedCapacityLinkedHashMap(int initialCapacity,
                                          float loadFactor,
                                          boolean accessOrder,
                                          int fixedCapacity) {
            super(initialCapacity, loadFactor, accessOrder);
            this.fixedCapacity = fixedCapacity;
        }

        /**
         * 重写LinkedHashMap的removeEldestEntry方法，因为LinkedHashMap的这个方法始终返回false，
         * 毕竟作为通用的实现，它也不知道使用者是希望使用固定大小的LRU缓存还是不固定的，所以人家给这个方法的修饰是protected，
         * 言下之意就是给具体使用者根据自己的场景来决定什么时候删除eldestEntry
         *
         * @param eldest
         * @return
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            //如果map中的元素数量超过了固定容量，就把最老的节点删掉
            if (super.size() > fixedCapacity) {
                return true;
            }

            return false;
        }
    }

    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU(int[][] operators, int k) {
        // write code here
        if (operators == null || operators.length == 0 || k <= 0) {
            return new int[0];
        }
        linkedHashMap = new FixedCapacityLinkedHashMap(k, 0.75f, true, k);

        List<Integer> retList = new LinkedList<>();
        for (int i = 0; i < operators.length; i++) {
            int[] commandArr = operators[i];
            if (commandArr == null) {
                continue;
            }

            //set操作
            if (commandArr.length == 3 && commandArr[0] == 1) {
                set(commandArr[1], commandArr[2]);
            }
            //get操作
            if (commandArr.length == 2 && commandArr[0] == 2) {
                retList.add(get(commandArr[1]));
            }
        }

        return retList.stream().mapToInt(Integer::valueOf).toArray();
    }

    private void set(Integer key, Integer value) {
        //HashMap的put方法会调用其putVal方法，会在方法后面调用afterNodeInsertion方法，evict传入的是true
        //LinkedHashMap重写了这个afterNodeInsertion，并且引入了一个protected方法调用——removeEldestEntry
        //给扩展者根据自己的场景来决定到底要不要删除eldestEntry
        linkedHashMap.put(key, value);
    }

    private Integer get(Integer key) {
        Integer ret = linkedHashMap.get(key);
        //如果不包含这个key，get返回的是null，我们要用-1替代，否则就返回具体的value
        return ret == null ? -1 : ret;
    }

    public static void main(String[] args) {
        LRUSolution lruSolution = new LRUSolution();
        int[] lru = lruSolution.LRU(new int[][] {new int[] {1, 1, 1}, new int[] {1, 2, 2},
                new int[] {1, 3, 2}, new int[] {2, 1}, new int[] {1, 4, 4}, new int[] {2, 2}
        }, 3);
        // 输出的正是官网给出的 [1,-1]
        System.out.println(Arrays.toString(lru));
    }
}


